The present invention pertains to the field of real-time processing of synchronous or isochronous data streams. More particularly, this invention relates to real-time processing of a synchronous or isochronous data stream in the presence of gaps in the data stream due to queue underflow or overflow.
In the field of data processing, xe2x80x9creal-timexe2x80x9d means that data that is available for processing at one predesignated time shall be completely processed by another predesignated time. A time-dependent sequence of data is commonly referred to as a xe2x80x9cdata streamxe2x80x9d where packets of data are transmitted from a sender to a receiver and are processed in sequence and in the same or a complementary manner at each endpoint. A synchronous data stream is one where the two endpoints share a common clock. An isochronous data stream is one where the two endpoints have equal, though not necessarily the same, clocks.
One example of a synchronous real-time data stream is data transmission between two modems. When transmitting data, a modem encodes digital data into an analog waveform at a particular real-time rate. A receiving modem decodes the analog waveform at a particular real-time rate to recover the digital data. Any interference with a real-time data stream may result in errors. For instance, a data transmission between two modems includes at least one training period. During a training period, the modems agree on various transmission parameters. Barring renegotiation, the modems rely on the agreed upon parameters to accurately send and receive data. If one modem fails to send data on time or drops data, synchronization between the two modems may be lost, rendering subsequent data unrecoverable.
Data queues are one source of potential failures in a real-time data stream. For instance, a transmitting modem may store data in an output queue prior to transmitting the data at a constant rate. If the modem transmits data faster than it stores data to the output queue, the output queue will underflow and cause an error in the data stream.
Conversely, a receiving modem receives data at a constant rate and may store the data in an input queue prior to further processing. If data are stored to the input queue faster than they are read from the input queue, the input queue will overflow and cause an error in the data stream.
Queue underflow and overflow are of particular concern when processing synchronous and isochronous data streams. This is because these data streams assume a reliable constant rate of service per unit of time. Queue underflow and overflow cause gaps in both synchronous and isochronous data streams and, depending upon the application, may substantially impact performance. For instance, modems may have to xe2x80x9cretrain,xe2x80x9d taking time to agree upon transmission parameters. The modems may also have to re-send un-recovered data. With data transmission rates on the order of tens or even hundreds of thousands of bits per second, wasting several seconds to re-establish communications is very costly in terms of performance.
Various techniques have been used to decrease the likelihood of gaps in synchronous data streams due to queue underflow and/or overflow. For instance, the size of the queues can be increased. Increasing the queue size, however, has the obvious disadvantage of using larger amounts of limited storage resources, and can be quite expensive. Furthermore, increasing the size of the queues can also increase the end-to-end delay, which is disadvantageous for certain classes of applications, including modems.
In another approach, as discussed in U.S. Pat. No. 5,721,830 issued to Yeh et al., data underflow is remedied by storing data in a circular buffer so that if new data is not available on time, old data can be reused. This type of approach is only applicable where re-using old data is preferable to sending no data at all, and has no application whatsoever to data overflow.
In one embodiment of the present invention, an output device sends a spurious data sample in place of a first data sample to be sent from a queue if the queue is in a state of underflow during which the first data sample is not available to be sent. The buffer is to store data samples for an isochronous data transmission. Circuitry skips the first data sample when the first data sample becomes available in the queue so that synchronization for subsequent data samples sent from the queue is preserved.
In another embodiment of the present invention, an input device advances an input buffer pointer to point to a next location in a memory in response to receiving a data sample at a queue during a state of overflow. The input buffer pointer indicates a location in the memory to which a next data sample is to be sent from the queue. The queue stores data samples for an isochronous data transmission. By advancing the input buffer pointer, synchronization for subsequent data samples is preserved.